0889. 根据前序和后序遍历构造二叉树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 递归

1. 📝 题目描述

• leetcode

给定两个整数数组，preorder 和 postorder，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

---

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2：

输入: preorder = [1], postorder = [1]
输出: [1]

---

提示：

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• preorder 中所有值都 不同
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• postorder 中所有值都 不同
• 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

2. 🎯 s.1 - 递归

c

struct TreeNode* build(int* pre, int ps, int pe, int* post, int os, int oe) {
    if (ps > pe) return NULL;
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = pre[ps]; root->left = NULL; root->right = NULL;
    if (ps == pe) return root;
    int leftVal = pre[ps + 1], leftSize = 0;
    for (int i = os; i <= oe; i++) { if (post[i] == leftVal) { leftSize = i - os + 1; break; } }
    root->left = build(pre, ps + 1, ps + leftSize, post, os, os + leftSize - 1);
    root->right = build(pre, ps + leftSize + 1, pe, post, os + leftSize, oe - 1);
    return root;
}

struct TreeNode* constructFromPrePost(int* preorder, int preorderSize, int* postorder, int postorderSize) {
    return build(preorder, 0, preorderSize - 1, postorder, 0, postorderSize - 1);
}

js

/**
 * @param {number[]} preorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var constructFromPrePost = function (preorder, postorder) {
  if (preorder.length === 0) return null
  const root = new TreeNode(preorder[0])
  if (preorder.length === 1) return root
  const leftVal = preorder[1]
  const leftSize = postorder.indexOf(leftVal) + 1
  root.left = constructFromPrePost(
    preorder.slice(1, 1 + leftSize),
    postorder.slice(0, leftSize),
  )
  root.right = constructFromPrePost(
    preorder.slice(1 + leftSize),
    postorder.slice(leftSize, -1),
  )
  return root
}

py

class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not preorder: return None
        root = TreeNode(preorder[0])
        if len(preorder) == 1: return root
        left_size = postorder.index(preorder[1]) + 1
        root.left = self.constructFromPrePost(preorder[1:1 + left_size], postorder[:left_size])
        root.right = self.constructFromPrePost(preorder[1 + left_size:], postorder[left_size:-1])
        return root

• 时间复杂度：$O(n^2)$，其中 n 是节点数，每次递归需查找 leftVal
• 空间复杂度：$O(n)$，递归栈深度

算法思路：

• 前序第一个为根，第二个为左子树根
• 在后序中找左子树根的位置，确定左子树大小，递归构建左右子树